package simple.linklist;

import struct.ListNode;

/**
 * 206. 反转链表
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * 示例 1：
 *   输入：head = [1,2,3,4,5]
 *   输出：[5,4,3,2,1]
 * 示例 2：
 *   输入：head = [1,2]
 *   输出：[2,1]
 * 示例 3：
 *   输入：head = []
 *   输出：[]
 * 提示：
 *   链表中节点的数目范围是 [0, 5000]
 *   -5000 <= Node.val <= 5000
 * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
 * @author 刘学松
 * @date 2022-03-25 10:01
 */
public class 反转链表 {
    /**
     * 迭代
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode tail = new ListNode(head.val);
        ListNode prv = new ListNode(head.val);
        while (head.next != null) {
            prv = new ListNode(head.next.val);
            prv.next = tail;
            tail = prv;
            head = head.next;
        }
        return prv;
    }


    /**
     * 递归
     * @param head
     * @return
     */
    public static ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prevNode = reverseList1(head.next);
        // 当前节点和next节点反转
        head.next.next = head;
        head.next = null;
        return prevNode;
    }
    public static void main(String[] args) {
        ListNode node = new ListNode();
        ListNode head = node;
        for (int i : new int[]{1, 2, 3, 4, 5}) {
            node.next = new ListNode(i);
            node = node.next;
        }
        ListNode p = head.next;
        p.next.next = p;
        p.next = null;
        System.out.println(p);
//        System.out.println(reverseList1(head.next));
    }
}
